package com.captjack.model;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Jack Sparrow
 * @version 1.0.0
 * @date 2022/10/21 08:27
 * package com.captjack.other
 */
public class Matrix {

    /**
     * 螺旋访问矩阵
     * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
     * 输出：[1,2,3,6,9,8,7,4,5]
     *
     * @param matrix 矩阵
     * @return 列表
     */
    public static List<Integer> spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return new ArrayList<>();
        }
        int row = matrix.length, col = matrix[0].length;
        // 访问过
        boolean[][] visited = new boolean[row][col];
        int total = row * col;
        // 右、下、左、上
        int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        // 方向索引
        int directionIndex = 0;
        int curX = 0, curY = 0;
        //
        List<Integer> list = new ArrayList<>(total);
        // 遍历
        for (int i = 0; i < total; i++) {
            visited[curX][curY] = true;
            //
            list.add(matrix[curX][curY]);
            // 计算下一个坐标
            int nextX = curX + directions[directionIndex][0], nextY = curY + directions[directionIndex][1];
            if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col || visited[nextX][nextY]) {
                // 自动转向
                directionIndex = (directionIndex + 1) % 4;
            }
            //
            curX += directions[directionIndex][0];
            curY += directions[directionIndex][1];
        }
        return list;
    }

}
